package com.example.demo.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/03/08 9:18
 */
public class _148_排序链表 {


    public static void main(String[] args) {
        ListNode node = new ListNode(-1, new ListNode(5, new ListNode(3, new ListNode(4, new ListNode(0)))));
        ListNode node1 = sortList(node);

        System.out.println(node1);
    }

    /**
     * 方法1：双层遍历
     * <p>
     * 外层遍历：遍历整个链表
     * <p>
     * 内层遍历：从外层遍历的当前节点开始，寻找出后续链表的最小值，然后与链表的头部节点的val值进行交换
     * <p>
     * <p>
     * 时间复杂度：O(n<sup>2</sup>)，n为链表的长度
     * 空间复杂度：O(1)
     *
     * @param head 链表头部
     * @return {@link ListNode}
     * @author WangYX
     * @date 2024/03/08 9:48
     */
    public static ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode res = head;
        while (head != null) {
            int min = Integer.MAX_VALUE;

            ListNode node = head;
            ListNode temp = head;

            while (node != null) {
                if (node.val <= min) {
                    min = node.val;
                    temp = node;
                }
                node = node.next;
            }

            temp.val = head.val;
            head.val = min;

            //最外层下次遍历
            head = head.next;
        }

        return res;
    }

    /**
     * 方法二：
     * <p>
     * 把链表所有节点存放入List中 <br>
     * 然后遍历List，重新组装链表。<br>
     * <p>
     * 时间复杂度：O(n)<br>
     * 空间复杂度：O(n)
     *
     * @param head 头节点
     * @return {@link ListNode}
     * @author WangYX
     * @date 2024/03/08 10:03
     */
    public static ListNode sortList1(ListNode head) {
        if (head == null) {
            return head;
        }

        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        list.sort(Integer::compare);

        ListNode res = new ListNode();
        ListNode temp = res;
        for (Integer item : list) {
            ListNode listNode = new ListNode(item);
            temp.next = listNode;
            temp = listNode;
        }
        return res.next;
    }

}
